COMMENT ⊗   VALID 00021 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.DEVICE XGP
C00005 00003	.PORTION MACROS
C00007 00004	.NSEC(ABSTRACT)
C00009 00005	.NSEC(MOTIVATION)
C00012 00006	.NSEC(TASK DOMAIN)
C00017 00007	.NSEC(TARGET PROGRAM)
C00023 00008	.NSEC(SIMULATED PROTOCOL)
C00034 00009	.NSEC(THE BEINGs SCHEME)
C00045 00010	.SSEC(The BEINGs present in PUP6)
C00057 00011	.NSEC(THE PARTS OF A BEING)
C00068 00012	.NSEC(DYNAMICS OF INTERACTING BEINGS)
C00072 00013	.NSEC(THEORETICAL ASPECTS OF PUP6)
C00079 00014	.NSEC(IDEAL and REAL SYSTEMS)
C00093 00015	.NSEC(QUESTIONS FOR AP SYSTEMS)
C00101 00016	.NSEC(EXCERPT: the synthesized CF program itself running)
C00108 00017	.NSEC(OTHER TASKS)
C00114 00018	.NSEC(NUMERICAL PERFORMANCE DATA)
C00118 00019	.NSEC(CONCLUSIONS)
C00131 00020	.NSEC(REFERENCES)
C00135 00021	.EVERY FOOTING(,,)
C00136 ENDMK
C⊗;
.DEVICE XGP
.COMMENT !XGPCOMMANDS←"/TMAR=9/PMAR=2185/BMAR=5";
.!XGPCOMMANDS←"/TMAR=100/PMAR=2185/BMAR=5";

.FONT 1 "BASL30"
.FONT 2 "BASB30"
.FONT 4  "BASI30"
.FONT 5  "NGR40"
.FONT 6  "NGR25"
.FONT 7  "NGR20"
.FONT 8  "GRFX35"
.TURN ON "↑α↓_π[]{"
.TURN ON "⊗" FOR "%"
.TURN ON "@" FOR "%"
.PAGE FRAME 66 HIGH 84 WIDE
.AREA TEXT LINES 1 TO 61
.TITLE AREA FOOTING LINE 66
.PLACE TEXT
.ODDLEFTBORDER ← EVENLEFTBORDER ← 5
.ODDLEFTBORDER ← EVENLEFTBORDER ← 500
.AT "ffi" ⊂ IF THISFONT ≤ 4 THEN "≠"  ELSE "fαfαi" ⊃;
.AT "ffl" ⊂ IF THISFONT ≤ 4 THEN "α∞" ELSE "fαfαl" ⊃;
.AT "ff"  ⊂ IF THISFONT ≤ 4 THEN "≥"  ELSE "fαf" ⊃;
.AT "fi"  ⊂ IF THISFONT ≤ 4 THEN "α≡" ELSE "fαi" ⊃;
.AT "fl"  ⊂ IF THISFONT ≤ 4 THEN "∨"  ELSE "fαl" ⊃;
.PORTION MACROS
.FILL
.TABBREAK
.SELECT 1

.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO BB ⊂ BEGIN NOFILL SELECT 6 SKIP 2 INDENT 0 GROUP ⊃
.MACRO B0 ⊂ BEGIN SELECT 8 NOFILL PREFACE 0 MILLS TURN OFF "→↑↓α"  GROUP ⊃
.MACRO E ⊂ APART END ⊃
.MACRO D ⊂ ONCE PREFACE 100 MILLS ⊃
.MACRO FAD ⊂FILL ADJUST COMPACT DOUBLE SPACE; PREFACE 2 ⊃
.MACRO FAS ⊂FILL ADJUST COMPACT SINGLE SPACE; PREFACE 1 ⊃
.FAS

.MACRO NSEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←0
.SECNUM←SECNUM+1 
.SEND CONTENTS ⊂
@1{SECNUM}. A⊗* ∞.→ {PAGE}
.⊃
.SECTION←"A"
.XGENLINES←XGENLINES-1
.GROUP SKIP 1
.ONCE CENTER TURN ON "{}"
@5↓_{SECNUM}. A_↓⊗*  
.  ⊃


.MACRO SSEC(A)  ⊂  TURN ON "{∞→"   
.SSECNUM←SSECNUM+1
.SEND CONTENTS ⊂
@7        A⊗* ∞.→ {PAGE}
.⊃
.ONCE INDENT 6 TURN ON "{}"
@2↓_{SECNUM}.{SSECNUM}. A_↓⊗*  
. ⊃

.COUNT PAGE
.SECNUM←0
.PAGE←0
.NEXT PAGE
.INDENT 0
.SELECT 1
.INSERT CONTENTS
.PORTION THESIS
.EVERY FOOTING(⊗7{DATE},Lenat,page  {PAGE}⊗*)
.ONCE CENTER
.NSEC(ABSTRACT)


Automatic programming must eventually deal with synthesizing large programs.
Using the paradigm of dialogue, a preliminary study was done on
automatically writing LISP programs tens of pages long,
requiring several hours of user-system interaction time to generate.
Many assumptions which are reasonable when concentrating upon tiny
targets become limiting factors in large dialogues. An experimental
system, PUP6, was constructed.  The methods it employs to generate
target code are not formal, but rather involve structuring of
knowledge about programming, about the chosen task domain (inductive
inference LISP programs), and about transfer of control.
Specification is via long, brittle dialogues with the user, but is
only partial: ambiguities are resolved by inference and deferral. 
Knowledge is represented as a pool of structured modules, whose
abilities include asking and answering questions posed by each other
and by the user.  Inadvertantly, PUP6 synthesized a new style of
concept formation program, one which can be interrupted as it runs
and queried about what it's doing.  This research revealed some major
difficulties the "next generation" of nonformal automatic program
synthesis systems must face. 

.GROUP SKIP 1
.NSEC(MOTIVATION)

Many AI researchers (e.g., see Section 4  of [Winston, 1974]) 
have experimented with 
systems which automatically write or modify
small programs, from partial specifications in an ambiguous 
language. They recognize
that larger capabilities are prerequisite to utility, but (correctly)
argue that mastery of toy tasks must precede mastery of real ones.
Efforts
to automatically
synthesize ⊗4large⊗* programs typically concentrate on
efficient but routine transformations, compilations
of well-specified programs in higher languages
(e.g., by heuristic compilers).  
	Despite the small chance for success in aiming at ambitious targets, it
it is dangerous to develop techniques applicable only to small tasks.
The analogy between understanding the
construction of a 10-line program, requiring five minutes of dialogue, and
understanding the
construction of a 100-page program, requiring five hours of dialogue, is at
best superficial.

.SKIP TO COLUMN 1

A system, PUP6, was partially implemented to study large 
code generation tasks. It did
ultimately synthesize three  LISP programs: a structural concept formation
program, a grammatical inference program, and a simple property
list maintenance routine (referred to as CF, GI, and PL). Some unanticipated
difficulties were encountered which may be inherent in syntheses of this
magnitude.

.NSEC(TASK DOMAIN)

	The task we considered was the generation
of large INTERLISP [Teitelman, 1974] programs, interactively, from long specific 
dialogues with a human user, in a quite
restricted subset of English. This activity will be referred to
as ⊗4automatic programming⊗*. 

This task can be made feasable by limiting the task domain of the ⊗4target
programs⊗*; that is, restricting the class of programs which the system is expected
to be able to write. In such a case, the advantage comes from
providing the system with a body of expert knowledge about that restricted
domain. 
	The first question to settle in such an endeavor is what the
⊗4target programs⊗* (the programs generated by the system)
are supposed to do, what their subject matter is, their task domain.
A large amount of effort was spent on this question, and the
chosen domain was inductive inference programs. The
obvious problem here is the size and sophistication of the targets, but there
are four big attractions:

.BEGIN PREFACE 0 INDENT 0,4,0 TURN OFF "-"
	(i)
A  wide  range  of  complexity  exists,  from  a  one-page   sequence
extrapolator   to   Meta-Dendral [Buchanan, 1972].
	(ii)   Each   increasingly
sophisticated inductive inference program  uses  
many  of  the  concepts  embodied  in
simpler  inductive inference programs.
	(iii) If a super-human target program is
ever written, it could itself contribute to the  field  of  Automatic
Programming! (This remark is humorous in the seventies, but may be
commonplace someday.)
	(iv)  Since people (especially scientific researchers)
are the inductive
inference experts, our reliance on  introspection  is  as
valid  --  and potentially as valuable -- as chemists' protocols were
to Meta-Dendral.
.END

After  studying  many  sample  programs  from  the inductive inference domain,
sequence extrapolation seemed the most reasonable  beginning
task. It was quickly learned that this was too easy: humans have only
a few techniques for extrapolating  sequences,  and  a  very  limited
capacity   for   composing   them.   Thus  a  rather  rigid  sequence
extrapolator writer may be capable of generating  a  large  class  of
super-human extrapolation programs (see section 4.2 on
Sequence-Extrapolator-Writer, in [Green, 1974]).
	The  next  candidates  were grammatical inference and concept
formation [Hempel, 1952].
Determined not to choose too simple  a  task  again,  concept formation
was finally decided upon.  The particular target was similar to Winston's
(Sec. 4.1 of [Winston, 1974]),
except his heuristic
graph-matching algorithm was simplified.

.NSEC(TARGET PROGRAM)

	It seems instructive now to describe in detail 
how CF, the  concept formation target  program synthesized by PUP6,
should operate. 
CF repeatedly scans a scene and tries to name it. As a first step, the scene
is broken into a set of objects and a set of features (relations on those
objects). Internally, CF maintains a model for each
concept (each
differently-named scene) it has ever
encountered. Each model contains (i) a description of the objects one expects in
such a structure, (ii) a set of features which ⊗4must⊗* be present in any scene
having this name, (iii) a set of feature which ⊗4must not⊗* be present if the scene
is to have this name, and (iv) a set of features which ⊗4may⊗* be present or
absent. Thus a model is an archetypical scene plus a name.
For example, part of a scene might be:     
.BEGIN NOFILL PREFACE 0  TABS 7,23 TURN ON "\" 
\⊗2OBJECTS⊗*\a,b,c,d
\⊗2RELATIONS⊗*\(Green a) (Blue c) (Touches c d) (Supports a c) (Supports b c)

CF's current model for an arch might be:      	   
\⊗2NAME⊗*\Arch
\⊗2OBJECTS⊗*\a,b,c
\⊗2MUST⊗*\(Supports a c) (Supports b c)
\⊗2MUSTNOT⊗*\(Touches a b)
\⊗2MAY⊗*\(Green a) (Wedge c) (Prism a) (Block b) (Parallel a b)
.E

Each time it is confronted by a new scene, CF  must
scan its models until it finds a model  which matches that scene. A model is said
to match a scene if all the MUST features associated with that model
are observed in the scene, and all the MUSTNOT  features  are
absent  from  the   scene. CF
informs the user of this guess,
and accepts the proper  name. If it  guessed  incorrectly,  CF
modifies its models. The wrong-guess model may have features added to
its MUST or MUSTNOT sets.  
This is sufficient to
prevent CF from making the same wrong guess twice in succession.
The correct-name model may have  to
be  modified or (if it's a new name) created and inserted into the
list of models, to ensure that CF will eventually learn that concept.

Suppose  that the target program reads in the above
scene fragment and
tries to match it to  the  above  ARCH model.  The  MUST
relations  should  all  be  present.   Yes,  the  scene  does contain
(SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT  relations  must
be absent from the scene. Sure enough, (TOUCHES a b) isn't there.  So
the model and scene are consistent, and CF announces that its
guess is ARCH.  
If the user verifies this guess,
then  the MAY set of the ARCH model
is augmented with the relations (BLUE c) and (TOUCHES c d), and
the OBJECTS set is augmented with "d."
	If the user denies that the scene is an arch, CF
finds a relation in the ARCH model's MAY set but not occurring
in the scene (e.g., (PARALLEL a b)), and then
transfers it from the MAY to the MUST set.  If no such feature 
existed, CF would look for a feature present in the scene
but not mentioned in any set of the ARCH model (e.g., (TOUCHES c d)), and insert
it into the MUSTNOT set.  In either case, the user would
be asked what the true name was, and that
model would have its MAY set augmented by any new 
features in the scene. Any features on  the true-name model's
MUST or MUSTNOT sets
which contradicted the scene would be transferred to the MAY set.

.NSEC(SIMULATED PROTOCOL)

	After the target concept formation program was specified,  it
was trimmed and then rewritten as a structured program. Next,
a complete dialogue was  simulated  between  the  user  and  a  human
programmer  (referred to as the system-player) playing the role of an
"intelligent"  automatic  programming  system  (similar   to,   e.g.,
[Balzer, 1972]).      The   system-player   kept   careful  records  as  he
programmed, and tried to create a bug-free  structured-program version of CF.

.SSEC(Excerpt from the simulated protocol)

Here is a piece of that dialogue. The context is as follows: the system-player
learns he must compare the input scene against
his internally-stored models of concepts, until he  finds  a model  which
passes the  comparison.   He  asks the user what it means for
a model to ⊗4fail⊗* the comparison to the input scene. That is, when can one
stop testing the given model and go on to the next model:
.XGENLINES←XGENLINES+1
.B0 TURN ON "∞→" NARROW 2,3
⊂∞α→⊃
.TURN ON "α"
~⊗1 SYS: Please type in a logical expression which is true iff we terminate the testing loop⊗*→~
~⊗1 USER:⊗* ⊗4Terminate iff any feature in model-features is incompatible with scene-features⊗*→~
~⊗1 SYS: SYS wants USER to type in a new name for specialized version of CONTRADICTS⊗*→~
~⊗1 USER:⊗* ⊗4IMPOSS⊗*→~
~⊗1 SYS: Move cursor to IMPOSS type of CONTRADICTS. I can no longer defer this decision:⊗*→~
~⊗1 	   A... Contradiction arises from features who have probability=1 of occurring⊗*→~
~⊗1	   B... Contradiction arises from features who have probability=0 of occurring⊗*→~
~⊗1	   C... Contradiction arises from features who have probability>0&<1 of occurring⊗*→~
~⊗1   Please type some sequence of some of the letters A,B,C; or type ?, Defer, or Details.⊗*→~
~⊗1 USER:⊗* ⊗4A, B, and C are all relevant.⊗*→~
~⊗1 SYS: I recommend: Each model's features be structured (along 1 dimension) into these 3 pieces:⊗*→~
~⊗1 	   PRESENT, which will hold features whose occurrence should have probability=1⊗*→~
~⊗1	   ABSENT,  which will hold features whose occurrence should have probability=0⊗*→~
~⊗1	   EITHER,  which will hold features whose occurrence should have any other probability⊗*→~
~⊗1   Please type back YES, NO, Unsure, Details, or three new names.⊗*→~
~⊗1 USER:⊗* ⊗4YES. Call them Must-be-present, Mustnot-be-present, May-be-present⊗*→~
~⊗1 SYS: Too long. Nicknamed MUST, MUSTNOT, MAY.⊗*→~
~⊗1 SYS: In all code generated to date, three references to model's features have been located.⊗*→~
~⊗1 SYS: In all cases, reference has been replaced by (APPEND MUST MUSTNOT MAY).⊗*→~
.TURN OFF "α"
%∞α→$
.END

Notice the tiny bit of creativity evinced by the system's recommendation 
to restructure the relations into MUST/MUSTNOT/MAY sets.
After hundreds of pages of this type of dialgoue, the CF program was finally completed
by the system-player.
The
dialogue  was  then annotated:     after each user response, comments
were inserted which described the "states" the system-player had gone
through before printing his next response.  This included blind paths
which were tried, use of outside world knowledge,  and,  in  general,
was  meant  to  be  the "reasoning" necessary to do the task.  The
fear was that a system could be built which synthesized CF,
yet  was  so unintelligent that nothing was
learned from it (e.g., see section 4.1 on PW1  in  [Green, 1974]).
Henceforth, "⊗4protocol⊗*" will
refer to this annotated user-player / system-player dialogue,
and "⊗4reasoning⊗*" will refer to the system-player's annotations.

.SSEC(Excerpt from the anotated protocol)


Here is the annotation which was filled in  between the line where the
user indicates that all three types of contradiction are relevant,
and the line where the system recommends structuring models' features into
three sets:
.XGENLINES←XGENLINES-1
.B0 TURN ON "∞→" NARROW 2,3
⊂∞α→⊃
.TURN ON "α"
~⊗1 1. I'll write the matching-test as a COND with three branches; the choice depends⊗*→~
~⊗1     on whether the model's feature is in the probability=0 part, or the⊗*→~
~⊗1     probability=1 part, or the in-between part of the model's features⊗*→~
~⊗1 2. A prob=0 contradiction means that a feature mustn't occur in the input scene, but it does.⊗*→~
~⊗1     A prob=1 contradiction means that a feaure should occur in the scene, but doesn't.⊗*→~
~⊗1     If the prob is strictly between 0 and 1, we have no way of being sure it is a contradiction.⊗*→~
~⊗1 3. One easy way that I could test which of the three kinds of model features I'm looking at⊗*→~
~⊗1     is if each model always keeps the three classes apart, either by tagging or as 3 subparts.⊗*→~
~⊗1	In the latter case, the whole set could be accessed as APPEND of the 3 subsets.⊗*→~
~⊗1 4. Let's see how the LISP code might look. Probability must either be =0,=1, or in between,⊗*→~
~⊗1     so the test in the last part of the COND is just T (i.e., "otherwise").⊗*→~
~⊗1     (COND ( if (MEMBER feature MUST-BE-PRESENT-part-of-model's-features) ⊗*→~
~⊗1	                 then contradiction iff (NOT (MEMBER feature input-scene's-features)))⊗*→~
~⊗1                 ( if (MEMBER feature MUST-BE-ABSENT-part-of-model's-features)⊗*→~
~⊗1	                 then contradiction iff (MEMBER feature input-scene's-features))⊗*→~
~⊗1 	            ( otherwise, no contradiction is possible))⊗*→~
~⊗1 5. I need some short names for these three subsets. Say PRESENT, ABSENT, EITHER.⊗*→~
~⊗1 6. Let me check with the user whether this restructuring and these three names are Okay.⊗*→~
~⊗1    I can do that by typing out a message to him on the teletype, and translating his reply.⊗*→~
.TURN OFF "α"
%∞α→$
.END

.XGENLINES←XGENLINES-1

	The central goals in writing PUP6 were that it
(i) correctly generate the target program CF,
(ii) follow the
protocol, and, most importantly, (iii) go
through  the  same  line of reasoning that the comments indicated the
system-player 
followed. 
PU6 would be
far along the road toward utility if it also  (iv)  could
write CF  from several dialogues, from several users, with
little preparation. PUP6 could not do this, but it wasn't designed to.
Future "marketable" systems will have to possess this flexibility.
	A corollary of this incremental annotated protocol approach is that the
abilities of the user must coincide with those  of  the  user-player  who
participated  in the protocol.  To be successful,
the user must be familiar
with  LISP,  well-grounded  in  computer  science,   and   have   the
input/output  behavior  of CF  very
clearly in his mind. The natural language front  end  is  so  brittle
that  the user must also phrase his responses very similarly to those
of the original protocol user-player.

.NSEC(THE BEINGs SCHEME)

	The next major design issue is the internal mechanism for
achieving this task.  The earlier PUP programs [Green, 1974] had taught the
author to organize the system knowledge in ways meaningful to how it
would be needed. This need for structuring is also echoed in [Minsky, 1972].
Many people, however [see Winston, 1974, and Newell, 1972], 
champion the merits of uniformity:
conceptually easy addition of new knowledge, and more
standardized (hence simpler) communication and interaction between
the knowledge.  Not wishing to give up these advantages, a compromise
mechanism, BEINGs, was developed.

Our automatic synthesis system, PUP6, will consist of a large  heterarchy of
knowledge modules. Each module, called a BEING,  is a specialist on some
tiny subject, 
a little expert
who can answer questions about his specialty.
In fact, asking and answering questions is the main activity of BEINGs.
So we view a BEING, a loosely-knit expert, as ⊗4equivalent⊗* to a set of questions
and corresponding responses. Each question is abbreviated to a single word,
and each response can actually be a little program which is run to obtain the
desired answer.
Thus the only parts of a BEING are his question/response pairs.
Each such part of a BEING is
an explanation of some facet of the BEING.  
In responding to
a question, all an answering-program may do is to (i) create a new BEING, 
(ii) tell some BEING how to
answer  some question (that is, modify some part of some BEING),
and (iii) ask questions (of itself, of other
BEINGs, of the human user interacting with  the system).

Our protocol was now cycled through again. 
This time, each comment the system-player had made was labelled with the ⊗4name⊗*
of some specialist who ought be able to interject that piece of knowledge at that
point in the dialogue. So the protocol was turned from a user/system dialogue
into a ⊗4script⊗*, where a hundred different experts (and one user)
cooperate to write a concept formation program.
Some of the experts who played the role of "watchdogs" were designated as
⊗4"demons"⊗*. This concept is explained in Section 3.2 of [Winston, 1974].


.SSEC(Excerpt from the script)

Here is how our  protocol excerpt 
(the same one as in Sections 5.1 and 5.2) now appeared in this script format:

.B0 TURN ON "∞→" NARROW 2,3
⊂∞α→⊃
.TURN ON "α"
~⊗1 Alternatives-expert: Since there are three alternatives, I will employ a COND:⊗*→~
~⊗1     (COND ( if (feature is the kind that must be present in the scene) ⊗*→~
~⊗1	                 then contradiction iff (prob=1 kind of contradiction exists))⊗*→~
~⊗1                 ( if (feature is the kind that must be absent from the scene)⊗*→~
~⊗1	                 then contradiction iff (prob=0 kind of contradiction exists))⊗*→~
~⊗1 	            ( if (feature is the kind that may be present or absent)⊗*→~
~⊗1	                 then contradiction iff (prob>0&<1 kind of contradiction exists)))⊗*→~
.APART
~⊗1 Contradiction-expert: If a feature has prob=1 of occurring in all instances of the⊗*→~
~⊗1     model, but it isn't present in the scene, then we have a contradiction.⊗*→~
~⊗1 Coding-expert: So prob=1 contradiction test is just (NOT (MEMBER  feature  scene))⊗*→~
~⊗1 Contradiction-expert: Analogously, a prob=0 contradiction means that some feature⊗*→~
~⊗1     must be absent from any instance, yet it is present in the input scene.⊗*→~
~⊗1 Coding-expert: So prob=0 contradiction test is just (MEMBER  feature  scene))⊗*→~
~⊗1 Contradiction-expert: If the probability of a feature occurring is strictly between 0⊗*→~
~⊗1     and 1, then I don't see how a contradiction might occur. Does anyone?⊗*→~
~⊗1 Negation-expert: Yes, I do. Can a feature and its negation be present in a scene ever?⊗*→~
~⊗1 Scene-expert: No, that will never happen.⊗*→~
~⊗1 Negation-expert: Forget it, then. I don't know of any additional way of contradiction.⊗*→~
~⊗1 Coding-expert: So prob>0&<1 contradiction test is just "NIL".⊗*→~
~⊗1 Manager: Let's move on to see how to encode the three dividing-tests of the COND.⊗*→~
~⊗1 Dividing-test-expert: One easy test is possible if a testing predicate is known already.⊗*→~
~⊗1 <no one responds to this plea, so Dividing-test-expert assumes that none exists>⊗*→~
~⊗1 Dividing-test-expert: Well, each test becomes just "Member" if all the features⊗*→~
~⊗1     passing a different branch of the COND belong to different sets. There must be a⊗*→~
~⊗1     fourth set, for those features passing no part of the COND, I think.⊗*→~
~⊗1     If these don't already exist, consider breaking the space into 4 subspaces.⊗*→~
~⊗1 Probability-expert: Not necessary. There is nothing left out of the 3 alternatives.⊗*→~
~⊗1 Alternatives-expert: Let me mention this hint: since all members of the space must⊗*→~
~⊗1	fall into one of the 3 categories, the final COND test can be guaranteed to be T.⊗*→~
~⊗1 Structure-inducing-expert: I can do the restructuring. Does any expert object?⊗*→~
~⊗1 <no one responds>⊗*→~
~⊗1 Structure-inducing-expert: All old occurrences of this space must be replaced by APPEND⊗*→~
~⊗1     of the three new model-features subspaces. Someone do that, please.⊗*→~
~⊗1 Finder: I have located all such occurrences, and tagged them.⊗*→~
~⊗1 Coding-expert: I have made the substitution that was requested.⊗*→~
.GROUP
~⊗1 Coding-expert: Including all these simplifications, the COND now looks like:⊗*→~
~⊗1     (COND ( if (MEMBER feature MUST-BE-PRESENT-part-of-model's-features) ⊗*→~
~⊗1	                 then contradiction iff (NOT (MEMBER feature input-scene's-features)))⊗*→~
~⊗1                 ( if (MEMBER feature MUST-BE-ABSENT-part-of-model's-features)⊗*→~
~⊗1	                 then contradiction iff (MEMBER feature input-scene's-features))⊗*→~
~⊗1 	            ( T NIL))⊗*→~
.APART
~⊗1 Long-name-demon: Those names are awfully long. Can you get me some shorter ones?⊗*→~
~⊗1 Plausible-name-proposer: How about PRESENT, ABSENT, and EITHER?⊗*→~
~⊗1 Manager: Must check with the user whether this restructuring and these names are Okay.⊗*→~
~⊗1 Messenger: I can do that by typing out a message to him on the teletype.⊗*→~
~⊗1 User:⊗* ⊗4OK, but call them Must-be-present, Mustnot-be-present, May-be-present⊗*→~
~⊗1 Long-name-demon: Those names are awfully long. Somebody get me some shorter ones.⊗*→~
~⊗1 Plausible-name-proposer: How about MUST, MUSTNOT, and MAY?⊗*→~
.TURN OFF "α"
%∞α→$
.END
.XGENLINES←XGENLINES-1
.SSEC(The BEINGs present in PUP6)

The protocol seemed to call for nearly a hundred different experts, which
meant that PUP6 would have to contain about a hundred BEINGs. Below is
that list of specialists. After each is a brief descriptive phrase and
two numbers which will be explained shortly.
The BEINGs are subdivided  into 
concept formation experts, programming experts, and generalists.

.BEGIN SELECT 6 NOFILL PREFACE 0

	⊗1A. BEINGs useful in writing inductive inference programs.⊗*

Psychologist. 582 cells. 18 parts. Eleven decisions to make about type of concept formation desired.
Classificatory-Concept-Formation. 37. 6. Partition a domain, in an interactive "guessing" manner.
Comparative-Concept-Formation. 45. 6. As above, then partially order the equiv. classes of the partition.
Metrical-Concept-Formation. 22. 4. As above, then induce a metric on the partial ordering of the classes.
Partition-a-Domain. 286. 16. In a guessing, interactive manner. 3 decisions about the flavor of the division.
Partition-by-take-element-get-class. 67. 9. Read in an ele, guess its name, check, update structures.
Partition-by-take-class-get-element. 40. 7. Read in concept name, guess its eles, check, update.
Partition-by-take-class-and-element. 64. 9. Read both scene and name, add to existing partition.
Recognize-contradiction. 226 cells. 11 parts. Notices phrases involving incompatibility. Three flavors.
Probability ≡ 0 Contradiction. 122. 10. Something should not occur but it does.
Probability ≡ 1 Contradiction. 106. 10. Something should occur but it doesn't.
Probability >0 AND <1 Contradiction. 118. 10. No restriction on x's appearance, so never a contradiction.
Scene. 48. 6. A data structure: objects, name, static relations, dynamic relations between objects.

	⊗1B. BEINGs useful in writing any kinds of programs.⊗*

Program-Manager. 631 cells. 17 parts. Doublecheck. Initialize, loop, finalize. Loop around 4 specific B's.
Fill-In-undefined-Section. 463. 14. Choose piece to encode, try; if fail, decide why and try to fix.
Clarify-Improbable-Situation. 2102. 13. Concentrate on some warning about quirk in existing code.
Support-and-Dump. 445. 11. After Pgm-manager finishes, dump new BEINGs and needed old ones onto file.
Make-Encodable. 162. 11. Last resort; replace B by an alternative or a generalization.
Encode. 1018. 12. Just a bookkeeper. Gather info, build schema, worry about args, call Make-Being.
Determine-Arg-Value. Locate where in the target pgm a given BEING will be called.
Flow-Preceded. Search through the target code and notice references to x.
Get-Data-Structure. 780. 13. Select type of repr., set it up, warn about modifications.
Select-Structure-Type. Bits of wisdom, e.g. "several weakly-interacting pieces indicate property list"
Element. 59. 8. All we know is that it is a member of a data structure.
Modify-Structure. 158. 12. Given ele., find which data structure it belongs to, insert or delete it.
Get-Hold-Of-the-Hard-Way. 301. 11. Guess (by Compute, Search, or Generate-and-test), then check.
Take-Hold-Of-the-Easy-Way. 505. 10. Via assignment to existing variable, or via reading it in.
Complex-Alteration. 498. 10. Initializing assignments, then modify substructures of given structure.
Conditional-Deletion. 878. 12. Decide what is to be deleted from where, and under what conditions.
Conditional-Insertion. 1244. 11. Decide what is to be inserted where, and under what conditions.
Some-Part-Of. 220. 11. Get simple destructive function, by inferring from examples or simple translation.
Joining-Function. 223. 13. Simple way of condensing results. Typically And, Or, Plus, Maximum.
Programming Knowledge stored in variables. How to defer and how to resolve these types of decisions:
	Adaptation, Known-Affects, Alternatives, Boolean, Define, Dichotomy, Predicate, Someof, Subsetof.
	How to terminate an AND loop, set up a Nested List, set up Property List.

	⊗1C. Generalists: domain-independent knowledge⊗*

Serve-the-User. 204 cells. 15 parts. Obtain info. until some of it is "executable", then carry it out.
Obtain-Usable-Information (Info-Obtainer). 199. 13. Choose from 4 ways to get new facts.
Use-Information. 148. 11. Pick best piece of info, try to execute it, repeat until successful.
Get-New-Info. 192. 15. Decide what is needed, make it specific, ask user, translate.
Extract-Relevant-Subset. 203. 13. Constrain what is being looked at; focus on relevant subpart.
Analyze-Implications. 276. 14. Locate affected area, predict affects, evaluate desirability.
Study-Type. 224. 11. If x is too general, ask x how to specialize x in this case. 
Make-New-Being. 461. 11. Simply accept info. about parts of new B, create one with those parts.
Search. 375. 13. Test each member of space; worry about termination criteria and behavior.
Generate-and-Test, and Compute, were never actually needed, and were therefore never coded.
Foreach. 938. 12. The iteration BEING. Minor decisions similar to those in Search.
Test. 269. 8. Threshhold of acceptability; decide whether result is ratio, ordinal, or just nominal.
Compare. 982. 12. Often by comparing subparts of the args pairwise, or by simple Joining function.
.XGENLINES←XGENLINES-1
Get-Name. 592 cells. 14 parts. Ask for plausible names for the new, specialized BEING; have user choose.
Propose-Plausible-Names. 356. 15. Apply: Initials, Mainwords, Firstfew, & compose these, to task descr.
Is-Of-Type. 143. 11. Predicate indicating containment. Too general to be powerful.
Choose-From. 312. 11. Select the best BEING and apply it; repeat until one succeeds.
Satisfy. 311. 18. Handles pattern-directed invocation. Broadcast plea, then Choose-from responders.
Messenger. 236. 15. Make user aware of x by printing x out (if not just done recently).
Translate. 328. 17. Broadcast to IDEN parts of all BEINGs, let the best responder take over.
Reinvestigate-Decision. 200. 13. Try to keep deferring a particular decision.
Defer-Decision. 289. 15. See When next it matters. If you can defer it, fine; if not, resolve it.
When-Next. 244. 12. Manipulate the decision, to find the situation where it matters.
Utilize. 328. 12. Apply knowledge rules until success. Called by When-Next.
Resolve-Decision. 184. 13. Trivial inference; then resort to asking the user.
Ask-User-About. 195. 12. Type out details of the decision, then interpret user's answer.
Better. 405. 13. Decide which of given 2 BEINGs should gain control, by asking them.
Handling of User Interrupts. Done by utility functions. User decides frequency of interrupts.
Long-name-demon. Watch out for unwieldy, long names, ask user for nickname.
Structure-inducing-demon. Replace testing for special subtype by physical restruc. along that dimension.
Natural Language Translation. Involves many simple BEINGs, besides Translate.
	Recognize-Args, Recognize-C*R, Recognize-Conditional, Recognize-Conjunction,
	Recognize-Equality, Recognize-Function-Returns, Recognize-Inclusion, Recognize-Literals,
	Recognize-Number, Recognize-Set-Relations, Recognize-Some Member, Add-Definition, 
	Adjective-Handler, Repeatedly, Recognize-Contradiction. 
	Also, there are several functions related to translation: e.g., Ungerundify, Plural, Opposite.
.END

.NSEC(THE PARTS OF A BEING)

The protocol script was cycled through yet again, this time observing what
kinds of questions the experts put to each other. Recall that each such
question would have to fit into a BEING part for the  expert who answered
it.

There seemed to be two major kinds of interactions: 
(i) recognizing self-relevance, estimating how difficult it would be for
oneself to answer a given question, how worthwhile the answer would be in
light of the current needs of the community, and 
(ii) introspecting, explaining how one is able to perform some given task,
at whatever level of detail is called for. These two classes further break
down into a total of 30 fairly specific classes of messages, listed in the
box below.
In the script, each BEING which was needed certainly wasn't called on in all 30
different ways. That is, to write CF, each BEING-part (question) was actually
needed by only about a third of all the BEINGs. The precise figure, for each
part, is given as a percentage in the box below. Looked at yet another way,
each BEING needed only about a third of the 30 possible parts in order to do his
job as specified by the script. The precise number that each BEING required
is listed  as the second number  in each line of 
the table of BEINGs in Section 6.2.
The first number there represents the ⊗4size⊗* of the BEING (the combined number of
list cells that were occupied by all its parts).


.XGENLINES←XGENLINES-2
.B0 TURN ON "→∞" NARROW 2,2
⊂∞α→⊃
.TURN ON "α↓_"
.SELECT 6
⊗8~⊗*						⊗2↓_BEING Parts_↓⊗* →⊗8~⊗*
⊗8~⊗*⊗2WHAT⊗* 82%  A brief summary of the global purpose, a template for an English phrase.→⊗8~⊗*
⊗8~⊗*⊗2WHY⊗* 77%  A justification of the BEING's existence, partly filled in by the BEING who called it.→⊗8~⊗*
⊗8~⊗*⊗2HOW⊗* 72%  A summary of the methods the BEING intends to employ. Global strategies.→⊗8~⊗*
⊗8~⊗*⊗2IDEN⊗* 54%  How this BEING is referenced in English phrases.→⊗8~⊗*
⊗8~⊗*⊗2WHEN⊗* 19%  Why this BEING should be given control now. The sum of weighted factors.→⊗8~⊗*
⊗8~⊗*⊗2ARGS⊗* 63%  Number of arguments; which are optional; names of any local variables.→⊗8~⊗*
⊗8~⊗*⊗2ARG-CHECK⊗* 81%  Predicates which examine each argument for suitability.→⊗8~⊗*
⊗8~⊗*⊗2EVAL-ARGS⊗*  4%  Which arguments are to be evaluated, and which quoted.→⊗8~⊗*
⊗8~⊗*⊗2REQUISITES⊗* 10%  If this BEING is actually chosen, what must be made true prior to (pre)→⊗8~⊗*
⊗8~⊗*		during (co), and after (post) execution.  Work to make these true (unlike ARG-CHECK).→⊗8~⊗*
⊗8~⊗*⊗2DEMONS⊗* 7%  Set of demons to be kept active while the BEING is in control.→⊗8~⊗*
⊗8~⊗*⊗2INHIBIT-DEMONS⊗*  5%  A lock/unlock mechanism, useful when handling demonic interrupts.→⊗8~⊗*
⊗8~⊗*⊗2EFFECTS⊗* 27%  What will probably be true after this BEING is through. What it achieves.→⊗8~⊗*
⊗8~⊗*⊗2RESULTS⊗* 15%  How many values this returns. What domain each is in. Side effects.→⊗8~⊗*
⊗8~⊗*⊗2META-CODE⊗* 70%  The body of the executable code, but with uninstantiated subparts.→⊗8~⊗*
⊗8~⊗*⊗2COMMENTS⊗* 16%  Hints for filling in undefined sections of other parts of this BEING.→⊗8~⊗*
⊗8~⊗*⊗2STRUCTURE⊗* 4% Viewing this BEING as a data structure, the operations doable to it.→⊗8~⊗*
⊗8~⊗*⊗2AFFECTS⊗* 14%  Other BEINGs which might be called by this BEING, and why.→⊗8~⊗*
⊗8~⊗*⊗2COMPLEXITY⊗* 92%  A vector of utility measures, including probable ease of calling, prob.→⊗8~⊗*
⊗8~⊗*		of success, prob. of (calling)* itself, time/space cost, efficiency of its output results.→⊗8~⊗*
⊗8~⊗*⊗2GENERALIZATIONS⊗* 27%  Some other BEINGs, encompassing this one.→⊗8~⊗*
⊗8~⊗*⊗2ALTERNATIVES⊗* 16%  Some similar or equivalent BEINGs (to try if this one fails).→⊗8~⊗*
⊗8~⊗*⊗2SPECIALIZATIONS⊗* 40%  How to write a streamlined, special-case version of this BEING.→⊗8~⊗*
⊗8~⊗*⊗2ENCODABLE⊗* 9%  How to order the evaluation of the other parts for self-streamlining.→⊗8~⊗*
.SELECT 8
.ONCE TURN OFF "α"
%∞α→$
.TURN OFF "∞→"
.END
.XGENLINES←XGENLINES-5

.SSEC(Internal Details)

We claimed earlier that BEINGs incorporate some aspects of both structure and
uniformity. Let us look them over and see how this is so.
Well, since each BEING has 10-30 parts, it's clear that
structure is present, all right. But what about the uniformity? It is
present in the fact that we have fixed our set of thirty questions.
If we had allowed each BEING to have whatever specific parts suited it best,
then to add a new BEING (write its parts) one would have to know
the particular questions he can ask each other BEING in the system (the names
of their parts), and
for  one BEING to communicate with another would require that it 
know precisely what that other BEING can be asked.  
	Of course the number of questions (parts) is arbitrary, but it
should not be ignored completely.  By choosing it to be ~1,
a completely uniform representation is obtained.
By allowing it to be ~1000, one could simply take the
union of all the individualized 
questions any BEING wanted, and thus all the uniformity
would disappear.  The number of parts each BEING has is therefore a parameter
expressing the degreee of compromise between structure and standardization
in the community of BEINGs.
	The specific BEING parts chosen have much to do with the
epistemology of programming.  
Although the particular set of thirty that I have chosen for the BEINGs in PUP6
is quite natural for writing CF, I certainly don't claim that they are 
the "right" questions for all automatic programming.

.ONCE TURN OFF "{}"
	The internal structure of the parts is not very interesting, and
will be treated lightly. The recognizing-self-relevance parts are
encoded as productions [Newell, 1972] which pattern-match against an assertional
data base [Reboh, 1974].
For example, the WHEN part of INFO-USER contains the production:
"If there is any New Information in the data base, then my urge to grab
control now is proportional to the number of such pieces".

.SKIP TO COLUMN 1

The introspection-explaining parts are simple programs.
For example, if asked how it transformed the English phrase
"Any feature is incompatible with the scene" into the BEINGs-language
.BEGIN PREFACE 0
⊗4"(Contradicts (Any Feature Model-features) Scene)"⊗*, the TRANSLATER will
answer:
.INDENT 3,3,0
 "I did it by asking all the BEINGs in the system who could recognize
that phrase. Contradicts recognized it, and said that I should work
recursively: (Contradicts <translation of "any feature">  <translation
of "the scene">).  The newly-constructed BEING named MODEL recognized
the first subphrase; likewise, the BEING named INPUT-SCENE
recognized the second subphrase."
.END

.NSEC(DYNAMICS OF INTERACTING BEINGS)

.SSEC(Control in the system)

The BEINGs in PUP6 control themselves in a very simple way.
The control structure repeatedly chooses the "best" 
part of the "best"
BEING, and either
executes it, accesses it, or fills it in (depending on why that part
was the one chosen). In the course of this activity, the "answering program"
in a part might request that some brand new BEING be created and initialized,
might ask other BEINGs for help, might make assertions, etc.
Whenever a new BEING is initialized, the system has 30 questions to answer
about it, 30 new little specific tasks that PUP6 will eventually attend to.
Choosing the "best" BEING means simply running all the BEINGs' recognition
parts, letting them examine the assertional world, and seeing which one feels
he is the most relevant. Choosing the "best" part is more routine: each BEING
generally wants its parts dealt with in some fixed order, so when BEING B is chosen,
B simply begins where it left off the last time it was chosen.

.SSEC(Using Domain-specific knowledge)

	Domain-specific knowledge is generally used to immediately
provide some needed piece of information. For example, PUP6 couldn't
make any sense out of the phrase "static concepts are left in the
subject's field of vision indefinitely", unless some BEINGs knew about
concept formation, and knew ⊗4enough⊗* to recognize that they were
relevant to interpreting the phrase.
	Sometimes, domain-specific knowledge is used in a more subtle,
delayed way. This takes the form of establishing a context or mental set.
For example, during the course of the dialogue which generated GI (the
grammatical inference program), the user mentioned to PUP6 the word
"grammar". The BEING who knows about grammars immediately recognized its
relevance, and one interesting thing it did was to
assert
"⊗4If  the  user ever mentions the word ⊗*⊗2test⊗*, ⊗4he may actually mean
⊗*⊗2parse⊗*".   This was placed in the IDEN  part of the TEST  BEING,  and  was
thus "demonized",  waiting  on  the  periphery  of  PUP6's
concentration.   It was in fact triggered later in the dialogue, as an
inference surprising to the user.

.NSEC(THEORETICAL ASPECTS OF PUP6)

	For aesthetic reasons, an effort was made to keep the languages for
PUP6 and CF the same. This meant PUP6 must write CF as a family of BEINGs.
Consequently ⊗4some⊗* BEING(s)
must write new BEINGs. The significant design issue here is
that the BEING  who  knows  about
⊗4X⊗*  takes  charge  of  generating  new BEINGs  relating to ⊗4X⊗*.  For
example,  the  INSERT  BEING  can  do  inserting  by  one  of  a  few
algorithms,  and  he  can  also  write (by specializing himself) more
specific  insert  routines,  and  he  can  answer   questions   about
inserting.

This idea is analogous to any reliance upon experts. The
SPECIALIZATIONS and ENCODABLE parts handle this chore.
An unusual consequence is that the synthesized code  will  have  all
the ⊗4types⊗* of abilities that any BEING community has:      it
can modify itself according to the user's
complaints  and  answer questions about what it is doing as it runs.
(An example session with the version of CF that PUP6 actually wrote is presented
in Section 12, ⊗4q.v.⊗*)
The CF program generated cannot, of course, write 
new programs, as  PUP6 can.
	In a similar vein, ⊗4each⊗* BEING must do the  translation
of  the  users' relevant quasi-English inputs into BEING-usable form. 
For example, our  INSERT  BEING  must  also  recognize  and
process phrases involving inserting, stack-pushing, and merging.
	PUP6 does not operate within the
exploratory anthropomorphic paradigm of programming 
(ignore details,  catch  them
later by debugging).  As in all programming, 
decisions continually crop up which
the system is not able to resolve  at  the  time. PUP6 always tries to
defer the decision as
long as possible.  When, at last, no progress can be made without its
resolution,  and  if the system is still unsure, then either the user
settles the question or else a backtrack point is reluctantly set up.
But  often,  by  this  time,  some  new  information is present which
enables the system to resolve the decision, thus reducing the  amount
of  backtracking.   If  there  are two or more decisions which can no
longer be deferred, the system tackles the easiest one first.
	It was hoped that most of the  carelessness
bugs could be eliminated through this deferral, feed-forward, and very
precise  record-keeping.  Humans  depend  on  their  adaptability  to
compensate  for limitations in their brain hardware
[Newell, 1972] but there is no
need for an ⊗4automatic⊗* programming system to do so.  For  example,
when  a  list  structure  is  first  encountered,  the system records
warnings that it is undefined, no accesses, insertions, or  deletions
have  been  observed,  and  so  on.  Each such worry is weighted, and
periodically PUP6 resolves such  warning  notes  --  especially
near the completion of the target program.
	Most  programmers  intentionally augment their code to aid in
later debugging, modification, and readability by humans.  These aids
are  typically  comments,  summaries,  over-generalized  subroutines,
optional print statements,  and  runtime  statistics.  Recently, the
structure  of  the  program  itself has also been
recognized as a powerful
manipulable element, affecting the accessability of the code, not just
its length or running time.
The length of any program written as a pool  of
BEINGs  is several times as long as a clean hand-coded version.  This
extra code, the parts of each new BEING which are superfluous, may be
viewed as organized self-documentation.  They should in theory improve the
debugging, expansion, and  accessibility  (to  alien  users)  of  the
synthesized code.
	Some assertions are so meaningful  to  the  user,
that they are stored in the code itself, as comments, even if they are
only temporary.  At any time, the user
may look at a piece of code; the comments present  ⊗4then⊗* are  all
assertions pertaining to that piece of code at that time.
BEINGS may use comments at  several  different  levels.  At  the
lowest  level,  each  comment  is  merely  a  unique token; it may be
inserted, removed, or searched  for.   Slightly  better,  the  BEINGs
system can ask "is there a comment involving ...". For this purpose, a
constrained syntax for the comments should be developed. Otherwise
(as, unfortunately, in PUP6) each new comment must be attended to
ad hoc.

.NSEC(IDEAL and REAL SYSTEMS)

	When imagining an ideal AP  (automatic  programming)  system, αα,
one  ability  we  might  wish  for  is  that  αα  be  able to input a
well-documented program, glean pure programming knowledge from it,
and  transform  this  into  a  format  αα  can use.  Also, to improve
itself, αα should be capable of digesting a sample, valid AP  dialog,
and (perhaps through additional user interaction) modify itself so αα
could actually carry on that  dialog.  
Another ideal to hope for is that the user be permitted to do whatever
he can whenever he can; if he suddenly thinks of a stray caution, αα
should accept it (e.g., "Oh, I might want to type in 
HALT instead of STOP, sometimes").
BEINGs were not designed with
these goals in mind, and as a result they may be an
insufficient framework for achieving them.
By studying the difficulties of PUP6,
isolating those due to poor programming from those due to
poor ideas, enough may be learned to build the next system one
qualitative step closer to this ideal αα.
It is in this spirit that BEINGs
are now contrasted against  the  concepts  of  ACTORs,
FRAMES, HACKER, formal AP systems, and macro expansion schemes.
	ACTORS [Hewitt, 1973]  provided  the  key  concept  of  integrating
uniformity  of  construction  with  sophistication of behavior.
Each ACTOR module has its own, unique interface, hence must be explicitly
aware of all the names and message formats
of all the  ACTORs it ever is going to shake hands with. 
Adding a new module is thus conceptually intricate as
well as practically difficult. 
Yet if one decrees a completely universal set of message types, then
most of them will be irrelevant to most modules. This is the price which
BEINGs pay.  This superfluity is real and almost
intolerable.
	FRAMES (Section 2.1 of [Winston, 1974])
seems superficially similar  to  BEINGs,  and
are so amorphous that they actually could subsume BEINGs. There is a
deep difference of philosophy and of intended usage, however.
FRAMES intentionally have default values already (with no processing)
filled in  for each frame, and replaced only when  necessary.
This  is  akin  to  automatic  programming by blind debugging, but is
antithetical to the fastidious bookkeeping BEINGs philosophy.  As  an
example,   consider   the   writing   of  a  short,  recursive
LISP program (reverse, flatten, factorial,  etc.)
A human, consulting the proper frame in his head, knows to ignore the
base step for a while, then fill it in, usually  as  ⊗4if  NIL,  then
NIL⊗*.  The
human makes this default synthesis, tries out the program, and  looks
closer  (to fill in this "slot" properly) only if something calls his
attention to it (such as a LISP error message:
NON-NUMERIC ARG  ⊗4NIL⊗*, e.g., if what was really needed was the base
step ⊗4if NIL, then 0⊗*).
A BEINGs system would
also  defer working on the base step, but could -- and would -- place
a note about that deferral into the assertional warning base.  Before
thinking  it  was  finished,  the  system  would  attend to that note
carefully. This is not a criticism:   
FRAMES are  meant  to 
model  perception, BEINGS are not.
	The contrast with HACKER (Section 4.3 in [Winston, 1974])
is similar to that with FRAMES.
The orientation of HACKER is to put together pieces of programs
into something close to the final desired target, then  try  and  run
it.  When  errors result, they are analyzed and then patched.  PUP6
is oriented toward writing bug-free code; what it writes must  always
coincide  with its internal specifications of that code. The user may
later change his mind, and the system should be (and occasionally
is) able to modify its
own  programs,  but  this  process  is much better defined than blind
debugging. On the other  hand,  if  PUP6 does  have  an
unexpected bug in it, it may be fatal. One
way to overcome this would be to include special recover-from-bugs
BEINGs into PUP6.
	The  formal  manipulation  systems which also synthesize code
are so different from BEINGs, that it is difficult to  compare  them.
These  logical systems [e.g., Buchanan, 1974] attack an entirely different
problem.  Their task is specified rigorously  in  advance,  and  they
proceed  formally  to  search  for  a  solution  program.  PUP6 is
designed to work from a much more
ambiguous specification, heuristically.  Each  action
is  implicitly justified by the fact that the user can later describe
to the system
what is undesirable about the program it's generated. 
That is, PUP6
may tolerate some  user ambiguity and error, at the expense of later having
to modify what it has written.
	Like  ⊗4any⊗* AP system which writes structured programs, the
external behavior  of  PUP6 is
reminiscent  of  macro  expansion regardless of ⊗4what⊗* the internal
BEING  interactions  are.  One  major  distinction  between  the  two
concepts is when and how the macros are expanded. Traditional answers
are:  at  compile  time,  by  rigid   substitutions.
BEINGs  systems expand their "macros" at
times they choose, using knowledge gleaned from each other  and  from
the  user. For example, consider a series of macro calls occurring in
the code: ⊗2(m↓1)(m↓2)(m↓3)⊗*. A macro expander could expand these in any order,
and the three activities could go on simultaneously, with no interference
or change in the final code. BEINGs would try to find some task common
to all three calls, and work on that first. The order of which to
first expand fully would be carefully weighed, 
and during that expansion new
information would be learned which could affect the expansions of the
other two function calls. The final code would ⊗4not⊗* simply be
⊗2APPEND(Expand(m↓1),Expand(m↓2),Expand(m↓3))⊗*,
as it would with a macro scheme.


The theoretical danger of BEINGs is that no small universal set of parts may be found; in
fact, this is why we specified our task (writing inductive inference LISP programs)
before deciding upon a set of BEING parts. Even so, each part was really only needed
by about one third of all the BEINGs in the PUP6 system, in order to successfully
synthesize CF.

BEINGs subsume (inefficiently) many popular AI features;
the demonstration will be brief:
A ⊗4demon⊗* could be replaced by a BEING whose ARG-CHECK predicate was the
triggering predicate, whose WHEN part was high enough to ensure frequent
attention, and whose META-CODE part was the body of the demon. An ⊗4assertion⊗*
in an associative data network
could be a BEING with only an IDEN part filled in; when it recognizes its
relevance, a fully instantiated assertion is returned. A ⊗4function⊗* is
equivalent to a BEING with only a META-CODE, ARGS, and EVAL-ARGS parts; one knows
almost nothing about it before executing it.
The inefficiencies should be clear: whenever a BEING throws a question open to the
floor, "Who can...", it takes an amount of time proportional to the number of
BEINGs in the system. One would introduce this huge time factor by 
replacing any of the above mechanisms by BEINGs.

The ⊗4number⊗* of BEING parts  seems to indicate 
the balance between uniformity and structure in the community.
This was touched on earlier in Section 7.1.
A small universal set of BEING parts is necessary to
preserve some of the advantages of uniformity
(easy addition of knowledge to the system, easy inter-BEING communication). This
demands that the number of parts of each BEING be, say, under 100. But it is
the complex structure of a BEING which makes complex behaviors feasable, including
flexible communication as well as viable final products. 
So each BEING should have many parts, say at least ten.
This range, 10 to 100, is wide for the domain of automatic programming. In other
domains, it may be narrow or disappear altogether; this would indicate that
BEINGs could ⊗4not⊗* be used effectively for those tasks.

Another way to view this is to examine the two possible extremes:
If each BEING may have only one part, then that part must answer
one universal question which
encompasses everything; this question must be of the form "tell me everything you
know," and means that we have a completely uniform formalism. At the other extreme,
each BEING has a separate part for each conceivable type of question it can answer;
all the uniformity has disappeared. 
We would then be left with a system where all we know about each entity is some
set of individualized assertions.
.NSEC(QUESTIONS FOR AP SYSTEMS)

	The success of an AI effort
can be assessed only where accepted standards of intelligence exist.
The  character of the dialogue (exemplified in sections 5.1, 5.2, 6.1)
is, of course, one important measure of the  intelligence
of  an  AP (automatic programming)
system.   One which asked "What is the first instruction?
What is the second...?" would be universal but worse than useless.
This  section  proposes some   questions  one  should  ask  when
confronted by a new AP system 
which generates code heuristically from a dialogue.
Capsule answers pertaining to PUP6 are parenthesized after each question;
fuller answers are located elsewhere.
	The questions break into two categories. First, one wants  to
know  what the system does.  Most important, does it synthesize a program?
(yes.)
If  so,  how  complex  is  that  task,  and  what  is   the   program
specification  like? (a concept formation program, 2000 lines long,
from one specific protocol dialogue).  
How precise must the user be:    may he err (no),
forget (no), change his mind? (in limited cases.) 
How detailed must his  dialogue  be? (by construction, just about as
detailed as if he were talking to a CS grad student programmer.) How
closely  does  the  dialogue determine the details of the final code?
(much of the 
final code is clearly determined by the precise user responses.)
How does the user know where he is during the dialogue? (simulated cursors
pointing to a graph representing synthesized code.)
Does the user ever get lost? (Often.)
	Quite  seriously, an important question is whether the system
writes a second program. (yes.)  
If so, how does it relate to the first  one
synthesized? (both are inductive inference LISP programs.) 
How much of the AP system is actually used in writing
⊗4both⊗* programs? (49 BEINGs out of 79.) 
One should ask what the full range of programs is
which  the system has successfully synthesized. (the concept former, the
grammatical inferrer, and the simple property list manipulation system.)
The dual questions to
these inquire whether a program may be generated by several different
(in the sense of rephrasing and in the sense of reordering the subtasks)
dialogues (theoretically, but not practically),  
and  what  the  range  of variability is. (theoretically large, but
practically quite limited.) Similarly, what
about the target language: is it a parameter? (no, always the same.) 
How does it  relate  to
the language the system is written in? (both written as BEINGs in 
INTERLISP.)
	Does the system modify as well as write code? (yes, but not
as its major mechanism.)   If so,  can
it  modify  anybody's,  or only those programs it has written itself?
(only its own, and only in simple ways.)
What is its "style" of programming? (many supplementary comments,
fairly clean structured programs written as BEINGs.)
One also wishes to know the  size
of  the tool as well as the size of the job: How does the system size
compare to target program size? (one order of magnitude larger.)
	Efficiency considerations are often the crucial
pragmatic ones. Economics and current hardware restrict the amount of
computation  which  may be done in toto; the expected lifetime of the
universe restricts us from using the  most "elegant" algorithms;  and
human  patience  restricts the interaction delay time (to a minute or
two of real time). One must therefore  ask  things  like
how  much  time  and  space  it  requires,  how long a delay there is
between user inputs, etc. (one CPU hour, 100K,  ≤1 CPU minute 
between responses, compiled INTERLISP run on a PDP-10 TENEX system.)
	The  second  class of questions concerns the theoretical side
of the AP system.  What new ideas is it meant to experiment with? 
(using BEINGs to write large programs).
How
do these ideas fare? (mixed results; this is the subject of
most of the remainder of this paper).
Does it write its code in the right way?
(it asks the right questions of  the  user  at  just  the  proper
times with respect to the original protocol.)
How does it manage this? (genesis directly from a protocol script.)
How extendable is it: how difficult is it to add new pieces
of knowledge and to modify old ones? (theoretically easy, practically it
requires familiarity with the system.)  Could  it  write  programs  in
various fields (possibly), in various styles (unlikely), in various sizes?
(the three target programs differ by about one order of magnitude.)
	How is knowledge  represented  internally? (BEINGs, assertions,
demons.)   Is  any  of  it
duplicated? (not much above the LISP language level; some universal
knowledge is factored out; e.g., how to CHOOSE-FROM a set of BEINGs.)
If so, why duplicated? (because too primitive to factor out; e.g.,
knowledge of how to bind variables.) 
.NSEC(EXCERPT: the synthesized CF program itself running)

In the earlier conversation excerpts, the simulated  user had no trouble
whatever understanding what the simulated experts asked him. In the actual
programmed PUP6 system, the human user who was sitting at the teletype quite
⊗4rarely⊗* understood what was wanted by the BEINGs. He frequently had to
interrupt them and ask them questions about who was in control, why, what
he was trying to do, what had recently transpired, etc. These ideally can
be phrased as simple retrievals and EVALs of active BEINGs' parts.
The BEING parts
most often called for by the user are the simple one-line "introspection"
templates. These include WHAT, HOW, WHY, and AFFECTS.  For 
theoretical reasons explained earlier,
the synthesized program, CF, was writen as a pool of BEINGs itself
(by PUP6, but not during the protocol. Actually, a fortuitous 
"bug" in PUP6 created this intriguing situation.)
Although its question-answering ability is inferior to PUP6, the fact that it
has ⊗4any⊗* such power was surprising to the author. In other words,
one can interrupt the target program as it is running
and ask questions. Any BEING on the control stack will provide fully instantiated
answers to any of its 29 allowable queries (its parts); all other BEINGs will provide only
hypothetical answers. As an example, consider this actual excerpt of a human
using the CF program synthesized by PUP6.
The characters of the dialogues with PUP6 to write CF, and with CF to
learn concepts, are similar; an "interrupted" excerpt of the user-PUP6
dialogue will be omitted.
(Some liberty has been taken with the
English; e.g., the user really types ⊗4WHAT?⊗*, not ⊗4What are you doing?⊗*).
"???" simply means "guess the name of the scene with these objects and relations".
CF types in ⊗4Italics⊗*, the user in ⊗2Boldface⊗*.

.B0 TURN ON "∞→" NARROW 1,1

⊂∞α→⊃
.TURN ON "α"
~⊗4READY TO ACCEPT BRAND NEW SCENE:⊗* ⊗2(??? (A B) (Block A) (Wedge B) (Touches A B))⊗*→~
~⊗4NOT AN ARCH. NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.⊗*→~
~⊗4WHAT IS IT REALLY?⊗*		   ⊗2Nothing⊗*→~
~⊗4TRANSFER FROM MAY TO MUST SETS OF ROW: (BLOCK  B)⊗*→~
~⊗4READY TO ACCEPT BRAND NEW SCENE:⊗*→~
.TURN OFF "α"
%∞α→$
.END

Here is the ⊗2same⊗* excerpt, but with the user interrupting occasionally.
"⊗2U:⊗*"
signifies he has interrupted,
and "⊗2OK.⊗*" signifies he has told CF "⊗2OK, go back to work now.⊗*"

.B0 TURN ON "↑↓∞→" NARROW 2,2 

⊂∞α→⊃
.TURN ON "α"
~	⊗2U:  What are you doing?⊗*→~
~⊗4CF:  Divide a domain into subdomains, using specialized version of PARTITION-DOMAIN.⊗*→~
~ 	⊗2How?⊗*→~
~⊗*CF:  By building up the partition gradually, by adding one <scene, name> pair.⊗*   ⊗2OK.⊗*→~
.APART
.GROUP
~→~
~⊗4READY TO ACCEPT BRAND NEW SCENE:⊗* ⊗2(??? (A B) (Block A) (Wedge B) (Touches A B))⊗*→~
~	⊗2U:  What are you doing?⊗*→~
~⊗4CF:  Break OBJECTS piece off (??? (A B) (Block A) (Wedge B) (Touches A B)) to examine.⊗*→~
~	⊗2What code is the current BEING going to execute?⊗*→~
~⊗4CF:  The meta-code of this SOME-PART-OF is (CADR arg1). Evals to (A B).⊗*  ⊗2OK.⊗*→~
.APART
.GROUP
~→~
~⊗4NOT AN ARCH.⊗*→~
~	⊗2U:  Why?⊗*→~
~⊗4CF: The ARCH MUST-relation (SUPPORTS A B) is contradicted in the SCENE.⊗*  ⊗2OK.⊗*→~
~⊗4NOT A TOWER. MIGHT BE A ROW.  MY GUESS IS ROW.⊗*→~
~⊗4WHAT IS IT REALLY?⊗*   ⊗2U:  Why are you asking?⊗*→~
~⊗4CF: CF cannot resolve it, and must at this time, so CF asks USER.⊗*→~
~	⊗2OK. What you wanted is:   Nothing⊗*→~
.APART
.GROUP
~→~
~	⊗2U:  What are you doing?⊗*→~
~⊗4CF: Go through space of concept names, and make user aware of changes.⊗*→~
~	⊗2What BEINGs might this affect?⊗*→~
~⊗4CF: MESSAGE is possibly called; some version of TEST is possibly called.⊗* ⊗2OK.⊗*→~
.APART
.GROUP
~→~
~⊗4TRANSFER FROM MAY TO MUST SETS OF ROW: (BLOCK  B)⊗*→~
~	⊗2U:  Why?⊗*→~
~⊗4CF: Change model of ROW until it contradicts the previous SCENE.⊗*  ⊗2OK.⊗*→~
~⊗4READY TO ACCEPT BRAND NEW SCENE:⊗*→~
.TURN OFF "α"
%∞α→$
.END
.XGENLINES←XGENLINES-1

.NSEC(OTHER TASKS)

One serious criticism of a large AI system turning out a much smaller product
is that it might only be able to do that one specific task.
An ability to write programs other than CF would indicate that PUP6 had
really captured the necessary knowledge involved, not just the necessary
responses to particular stimuli. The results were inconclusive. Two
new target programs were specified and then quickly synthesized, 
but a few new BEINGs had to
be added to PUP6, and the synthesizing dialogues were awkward.
	Let  us  briefly  describe  GI  and  PL, the second and
third programs PUP6 synthesized.   GI  is  a  simple
grammatical inference program. It builds up a set of plausible  rules,
rather  than  enumerating  through  the space of all grammars. Yet it
lacks most of the "tricks" of  the  best  g.i.  programs.   The  user
repeatedly specifies a string, labelled LEGAL, ILLEGAL, or ??. In the
latter case, GI must print out its guess and accept the correct label
from  the  user.   In  all  three  cases,  it  must update its set of
plausible rules to be at  least  consistent  with  all  positive  and
negative  instances  observed. In some versions of GI which the user coaxes
PUP6 to generate, a parse tree may be maintained  and  inspected;  in
other versions, just a list of the rules used during a parse is kept.
	PL is a data-retrieval-on-keys system, which maintains a
property list structure.
The user repeatedly types
in a request to insert, delete, or inspect a  record  (e.g.,  INSERT:
PASSENGER  Jones  FLIGHT  741  FROM SFO TO LAX CARRIER TWA LEAVE 7:15
ARRIVE 8:00).  Any unspecified fields are treated  as  don't  cares;
thus the request is matched against entries in the data base.
.BEGIN GROUP
	The table below shows how each type of knowledge was used  in
writing the three target programs.  All numbers refer to BEINGs.

.NOFILL INDENT 0 SELECT 6 TABS 20,25,30,35,40,45,50,55,60,65,71,78,83 TURN ON "\"

⊗2TYPE⊗*\⊗5U  S  E  D     I  N     S  Y  N  T  H  E  S  I  Z  I  N  G⊗*         
⊗2OF⊗*
⊗2KNOWLEDGE⊗*\ CF\ CF\ CF\ CF\ GI\ PL\ not\Crea\Crea\Crea\Total\Total
\ GI\ GI\ PL\only\only\only\used\-ted\-ted\-ted\Beings\Beings
\ PL\only\only\\\\ever\in CF\in GI\in PL\\in PUP6

Programming\ 39\  7\  5\  5\  3\  1\ 14\ 52\ 27\ 21\174\ 74
Domain-Specific\  0\  3\  0\  9\  8\  1\  5\  4\ 10\  3\ 43\ 26
Total BEINGs\ 39\ 10\  5\ 14\ 11\  2\ 19\ 56\ 37\ 24\217\100
.END

"Created" means "written by PUP6 during the dialogue which synthesized".
Notice the percentage of programming BEINGs  which  were used in  all
three dialogues (39/74). The three domain-specific BEINGs used
in both CF and GI  sessions  indicate  that  they  may  be  Inductive
Inference  domain specific.  
They aren't used in PL, which is not an
inductive inference task.
All three of these BEINGs deal with partitioning a domain.

Although BEINGs can theoretically handle
user errors, PUP6 was set up expecting that the user would never  err
or  forget.  He could, after the program was finished, try it out and
describe how he wished it changed. Occasionally, PUP6  actually  make
the  right modifications. For example, 
after the synthesis of PL is finished, the user tries
out the program and finds that he is unable to delete more  than  one
reservation  with  any  single  command. He complains about this, and
PUP6 modifies the program so that he may specify a pattern,  and  all
reservations  matching  that  pattern  will  be  purged.   
There is only one English sentence, however, which is able to effect this change; 
the slightest deviation would cause PUP6 to  misunderstand it!

.NSEC(NUMERICAL PERFORMANCE DATA)

	Good measures  of  concentration  of intelligence are not yet
available.  The only alternative is to present  ephemeral  numerical
efficiency  data,  which now follows. PUP6 is 200 pages long when
PRETTY-PRINTED, and has synthesized three programs, 7, 20, and 30
pages long (1, 4, and 6 pages, when coded by hand.)
	Two important factors are omitted when simply comparing system
and target lengths. First, one might improve any such measure by simply
decreasing the size of a given system. This is certainly wrong, since, e.g., 
removing all the comments from a program shouldn't increase its
intelligence rating!  Secondly, the total volume of distinct target programs
should be considered. Compilers turn out programs small compared to
themselves, but are valuable because of the vast variety of such programs
they can put together.
This factor reflects how much of the "insides" of the system can be used in
writing many different programs.
	PUP6  takes  60  cpu minutes to produce CF (compiled INTERLISP
code, run on a PDP-10 TENEX system). During this time,
300K characters get typed out to the user, who  reponds  with  about
4K  himself. The dialogue lengths are best specified in characters,
since often the user will supply simply a number or  a  letter  or  a
YES/NO  reply.
Even  the  character  counts  are
very  rough,  because  the  format  of  the AP dialogue can easily be
varied by a couple orders of magnitude.  The mean wait time  (between
the user's input and the next machine output) is about 10 seconds. The
longest delay  between  successive  user  inputs  is  1  CPU  minute.
Unfortunately,  PUP6  requires 100K to run in, which (with INTERLISP)
exhausts the virtual memory of the current hardware being  used.  One
would lose vast amounts of time by using intermediate storage devices
or by running consecutive communicating jobs. Efficient use of multiple
processors and of extended core storage might be made.
	PL  was  one fifth the size of CF, and took about a seventh
as long to generate. The dialogue was shorter by only 
a factor of three. The
dialogue for the CF target program was  long and tiresome; the problem
was even more acute for the PL program.

.NSEC(CONCLUSIONS)

	The  main  successes  of the experiment were that the desired
reasoning steps in the original protocol
were actually simulated, most of the BEINGs were used
in  writing  more  than one of the programs, and the synthesized code
could be interrupted and asked a few kinds of  questions.   The  main
defects  were  the  inflexibility of the system to new dialogues, the
inability for  the  user  to  add  new,  high-level,  domain-specific
knowledge,  the verbosity of the system, and its ill-founded dependence on
user reliability.  These problems seem to
be inherent in the task of nonformal automatic synthesis of large programs.
The small fraction of parts which were actually relevant to each BEING (a
third) indicates that this scheme should be used as one mechanism in 
some AI systems, but not as the sole curator of information and control.
	The  fact  that target code is in the format of BEINGs limits
the size of the target programs (⊗7≥⊗* one page) and their efficiency  (a
BEING-call  is a very slow and intricate process) and of course their
style. The most startling result -- which should have been forseen --
was that the synthesized code has all the properties of BEINGs.
This was mentioned
casually earlier, 
but is worth restating: the generated code
is  self-commenting  in the strong sense that it
can answer any
(of our set of 29) questions about itself.  Those which make sense at
compile-time  can  be  asked  then;  those  which  make  sense during
execution may be asked then.
(See again the session presented in Section 12).
	The set of questions the user was expected to want to ask the
system  is  similar  to the questions one BEING wants to ask another.
So when the "nice" user interrupts, his questions are almost always a
simple  retrieval  from a property list 
When the average  user  interrupts,  his  questions  are
often unintelligible to PUP6.
	Meaningful use of comments proved helpful. As an example, the
comment at the end of the main outer loop was "COMMENT, INFINITE LOOP
IN THIS PROG" for most of the CF-producing session. Near the  end
of  the  dialogue, the  CLARIFY-IMPROBABLE-SITUATION BEING recognizes
this as a warning, works on introducing a breakaway  test,  and  then
replaces  the  comment by one indicating that no infinite loop exists
there anymore.   The  advantage  of  embedding  our
insertions in the code in this way is that, at any stage, the user can
inspect the code and get something meaningful  out  of  the  comments
which are present.
	The  careful  bookkeeping   actually   did   eliminate   some
carelessness  errors, though it had no effect on user errors or later
program maintenance  directives.  This   last    process     is  less
ill-defined  than  blind debugging, and in fact is  similar to
programming itself.  The deferral  of  decisions  has  the
corollary of reducing (though not minimizing) communication with
the slow user channel.
	Synthesizing a new, 
clean target program  probably  would  require
adding  a  few domain-independent BEINGs and several domain-specific
BEINGs, and generalizing a few parts of  some  existing  BEINGs.
Hopefully, no new part would need be added to BEING anatomy.
Since  the  dialogues  for  GI  and PL were not studied before-hand,
their acceptability  would  have  demonstrated  the  success  of  the
system.  Most of the existing BEINGs were used in generating these
new programs, but a few new BEINGs had to be added. This addition
process required some detailed knowledge of the PUP6 system, not just of
the domain.  Equally
discouraging, the dialogue to write PL is too long and detailed
for the task at hand.  It also  seems  that  the  front  end  is  too
brittle  to  allow  anyone  unfamiliar with the system to easily work
with it.
	The need for flexible communication stems  only
partially from inter-user  differences.   A  serious  and  unexpected
source  of  conflict  here  is the amount of inference the user wants
done.  This level is relatively subjective, and may fluctuate rapidly
even  with  one  user  writing one program. Perhaps there should be a
dial he can set. At one extreme, the system would  ask  the  user  to
verify  even  the  most  trivial  inductions.  At  the  other extreme
setting, the system would probably write  the  target  program  after
just a few brief user inputs. The user would then try out one program
after another, interjecting just one or two comments each time, after
which  the  system would come up with the next version.  This program
modification mode seems appropriate for someone ignorant of LISP, who
nevertheless has the I/O behavior of his target clearly in mind.
	Some of the BEING parts  proved  embarrassingly  unnecessary.
The  CO-REQUISITES  part was never used.  The only activity which had
to be done concurrently was demon activation. The AFFECTS part was of
interest  to  the  user  occasionally,  but  never to any BEING.  The
EFFECTS part originally had a twin, describing what would  happen  if
each  BEING  were  ⊗4not⊗*  called right now.  In each case, this was
merely a trivial restatement of the frame problem.  So,  like  STRIPS,
PUP6  ignores  the  frame  problem:     all changes must be
explicit.
	Much  of PUP6's comments are boring and unnecessary; this was
felt to be an engineering problem which would be ignored in all but a
"marketable"  AP system. This view was probably incorrect. One of the
most severe AP problems is having  the  system  inform  the  user  of
precisely  what  he should know -- no more nor less.  This requires a
sophisticated  user  model  cleverly  interfaced   to   the   current
programming task.
	Another problem with large, long dialogues is user  error.  A
human  has  great  difficulty keeping "on top" of everything.  He may
get lost, forget, change his  mind,  or  misunderstand.  Again,  this
problem  was originally considered ignorable, but has shown itself to
be  a  limiting  practical  factor  in  wide  accessability.  It  was
necessary  to  create  a  forgetful-user  demon  to prevent anaphoric
reference to something which, though uniquely determined, hadn't been
mentioned within the past several seconds of real time.
Related to this is the problem of keeping
the user informed of where he is. PUP6 simulated a continuous display
of  the graph of the current partial program, augmented by static and
dynamic cursors. This  simple 
use  of  dynamic  and  textual  indices  seems
insufficient.   The  user was still often confused, wishing a section
of the partially synthesized CF code referred to not by pointing, not by name,
but rather by a brief, meaningful (to him
only!)  phrase.   This may also be one of the major AP (automatic
programming) problems which
must be studied further.
	Will we ever need a
system whose target programs will be longer and more complex than the
system  itself?
Why couldn't we settle for a truly intelligent
AP system several times as large as anything it
could produce?
Worries  about large dialogues arise because future AP
systems are viewed as tools for writing programs which humans  simply
cannot  manage  currently:      viable natural language systems, huge
operating systems, better AP systems.
Is there any evidence that such hyper-productive systems could ever
be written? There seems
to be a manageable body of information which one needs master
to do programming.  One can
write  programs  as complex as he wishes if the program is designed in a
clean way. Thus the size of AP systems will probably
level  off  (albeit  huge
compared  to  existing  programs)  even as the size and complexity of
their generated code continues to increase and,  eventually,  surpass
them.

.B

.E
.ONCE CENTER
.NSEC(REFERENCES)

.BEGIN INDENT 0,5,0  TURN OFF "-"

Balzer, R., 1972, ⊗4Automatic Programming⊗*, Institute Technical
Memorandum,  University of Southern California
Information Sciences Institute.

Buchanan, B., Feigenbaum, and Sridharan, 1972, ⊗4Heuristic Theory Formation⊗*,
Machine Intelligence 7, pp.267-280. 

Buchanan, J., and D. Luckham, 1974, ⊗4On Automating the Construction of Programs⊗*,
Memo AIM-236,
CS Report STAN-CS-74-433, Artificial Intelligence Laboratory,
Stanford University.

Green,C., R. Waldinger, D. Barstow, R. Elschlager, D. Lenat, B. McCune, 
D. Shaw, and
L. Steinberg, 1974,
⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
CS Report STAN-CS-74-444, Artificial Intelligence Laboratory,
Stanford University.

Hempel, C., 1952, ⊗4Fundamentals of Concept Formation in
Empirical Science⊗*, University of Chicago.

Hewitt, C., 1973, ⊗4A Universal Modular ACTOR Formalism for
Artificial Intelligence⊗*, 3rd International Joint Conference on
Artificial Intelligence,
pp. 235-245.

Minsky, M., and S. Papert, 1972, ⊗4Artificial
Intelligence Progress Report⊗*, MIT Project MAC, AI Memo 252.

Newell, A., and H. Simon, 1972, ⊗4Human Problem Solving⊗*, (Prentice-Hall).

Reboh, R., and E. Sacerdoti, 1974, ⊗4A Preliminary QLISP Manual⊗*,
SRI, Menlo Park, Ca.

Teitelman, W., 1974, ⊗4INTERLISP Reference
Manual⊗*, XEROX PARC, Palo Alto, Ca.

Winston et al., 1974, ⊗4New Progress in Artificial Intelligence⊗*, MIT AI
Lab Report AI-TR-310.

.END

.SSEC(Acknowledgements)

The ideas and the system described use concepts from ACTORS, 
heterarchy, structured programming, assertional data bases,
flexible data types, pattern-directed invocation of procedural
knowledge, the paradigm of dialogue, studies on program specification,
QLISP, INTERLISP, LISP, English,... In particular, the author  
drew heavily from creative discussions with C. Green, R. Waldinger,
D. Barstow, B. McCune, D. Shaw, E. Sacerdoti, and L. Steinberg.
Computer time for the research was generously provided by the
Artificial Intelligence Center of SRI.

.EVERY FOOTING(,,)
.PORTION CONTENTS
.NOFILL
.BEGIN CENTER
.GROUP SKIP 3

⊗5↓_BEINGS:_↓⊗*


⊗5SYNTHESIS OF LARGE PROGRAMS FROM SPECIFIC DIALOGUES⊗*





⊗2Douglas B. Lenat

Stanford Artificial Intelligence Laboratory
Stanford, California, USA⊗*


.END
.PREFACE 10 MILLS
.TURN ON "{∞→"
.NARROW 11,11
.SKIP 2
.RECEIVE

.BEGIN CENTER


⊗7{DATE}
.END